# 插入区间: https://leetcode-cn.com/problems/insert-interval/

# 和合并数组是一样的
class Solution:
    def insert(self, intervals: list, newInterval: list) -> list:
        """
            直接模拟
        """
        i, n = 0, len(intervals)
        rst = []
        # 1. 区间结束小于 要插入区间开始的，直接加进去
        while i < n and intervals[i][1] < newInterval[0]:
            rst.append(intervals[i])
            i += 1

        # 2. 下面的肯定是区间的结尾要大于 newInterval[0]开始。 那么确定左边界和右边界
        # 可能跨好几个区间
        while i < n and intervals[i][0] <= newInterval[1]:
            newInterval[0] = min(intervals[i][0], newInterval[0])
            newInterval[1] = max(intervals[i][1], newInterval[1])
            i += 1

        # 3. 将合并后的区间加入到结果集
        rst.append(newInterval)

        # 4. 将剩下的区间放到结果集里
        while i < n: rst.append(intervals[i]); i += 1

        return rst